#include "StdAfx.h"
#include "StrokeVertexesFinder.h"
#include "DistinctivePoint.h"
#include <assert.h>

const float kDiscrepancyCriterion = 0.2f * 0.2f;

//-------------------------------------------------------------------------
StrokeVertexesFinder::StrokeVertexesFinder(
	NeighborEnumerator& inNeighboEnumerator)
	:  mNeighborEnumerator(inNeighboEnumerator)
{
	mNumberOfDiscardedVertexes = 0;
	mLimitForArcParameter = 1.0f / mNeighborEnumerator.GetDistanceCriterion();
}

void StrokeVertexesFinder::AddVertexesForStrokeEnds(const Stroke& inStroke)
{
	if (!inStroke.IsClosed())
	{
		AddEndsMeeting(inStroke, Stroke::kBeforeFront);
		AddEndsMeeting(inStroke, Stroke::kAfterEnd);
	}
}

void StrokeVertexesFinder::AddVertexesForStroke(const Stroke& inStroke)
{
	Stroke::ConstDotIterator it = inStroke.mDots.begin();
	const Stroke::ConstDotIterator itEnd = inStroke.mDots.end();
	assert(itEnd != it);

	int index = 0;
	const ContourDot* dot = &(*it);
	const ContourDot* prevDot = NULL;
	const ContourDot* prev2 = NULL;
	const ContourDot* prev3 = NULL;

	while (++it != itEnd)
	{
		prev3 = prev2;
		prev2 = prevDot;
		prevDot = dot;
		dot = &(*it);

		if (mNeighborEnumerator.SelectNeighbors(*prevDot, false))
		{
			Curve curve(*prevDot, *dot, &inStroke, index);
			AddTPoints(curve); // using the selection of neighbors inside
		}
		AddCorner(prev3, prev2, prevDot, dot, inStroke, index + 1);

		++index;	
	}
	if (inStroke.IsClosed())
	{
		// process the curve that connects end of the stroke to it's beginning
		prev3 = prev2;
		prev2 = prevDot;
		prevDot = dot;
		dot = &inStroke.mDots.front();
		if (mNeighborEnumerator.SelectNeighbors(*prevDot, false))
		{
			Curve curve(*prevDot, *dot, &inStroke, index);
			AddTPoints(curve);
		}
		AddCorner(prev3, prev2, prevDot, dot, inStroke, index);
	}
}

void StrokeVertexesFinder::PruneMultipleIntersections()
{
	// delete ends meetings behind the T-point
	for (TPointCollection::iterator itp = mTPointInfos.begin();
		itp != mTPointInfos.end(); ++itp)
	{
		const ArcInfo* arcInfo = itp->arcInfo;
		for (int i = arcInfo->firstIndex; kInvalidIndex != i;)
		{
			TwoEndsInfo& tei = mTwoEndsInfos[i];
			bool isTwoEndsDeleted = false;
			if (!tei.isDeleted)
			{
				bool isTwoEndsDeleted = tei.DeleteIfSmallerParameter(arcInfo, itp->s);
				mNumberOfDiscardedVertexes += isTwoEndsDeleted;
				if (!isTwoEndsDeleted && !itp->isDeleted)
				{
					// may be the the two-ends meeting at one side of stroke
					// in this case the T-point should be discarded
					if (!itp->curve.AreDotsSeparated(*tei.arcInfo1->info->dot,
						*tei.arcInfo2->info->dot))
					{
						itp->isDeleted = true;
						++mNumberOfDiscardedVertexes;
					}
				}
			}

			i = tei.NextIndexFor(arcInfo);
		}
	}
}

int StrokeVertexesFinder::GetNumberOfVertexes() const
{
	return mTPointInfos.size() + mTwoEndsInfos.size() + mCorners.size()
		- mNumberOfDiscardedVertexes;
}

void StrokeVertexesFinder::GetVertexes(DistinctivePoint* outBuffer) const
{
	DistinctivePoint* q = GetTPoints(outBuffer);
	q = GetEndsMeetings(q);
	GetCorners(q);
}

int StrokeVertexesFinder::GetNumberOfJunctions() const
{
	return mJunctions.size();
}

void StrokeVertexesFinder::GetJunctions(Junction* outBuffer) const
{
	Junction* q = outBuffer;
	for (JunctionCollection::const_iterator ij = mJunctions.begin();
		ij != mJunctions.end(); ++ij, ++q)
	{
		q->strokes[0] = ij->first->info->stroke;
		q->strokeEnds[0] = ij->first->info->strokeEnd;
		q->strokes[1] = ij->second->info->stroke;
		q->strokeEnds[1] = ij->second->info->strokeEnd;
	}
}

//-------- private ------------------
void StrokeVertexesFinder::AddTPoints(const Curve& inCurve)
{
	while (const NeighborEnumerator::Info* info = 
		mNeighborEnumerator.FindNextNeighbor())
	{
		bool reverseDotDirection = 
			(Stroke::kBeforeFront == info->strokeEnd);
		float t = inCurve.FindParameterAimedByContourDot(*(info->dot), 
			reverseDotDirection);
		if (t < 0)
		{
			continue;
		}
		ArcInfo* arcInfo = GetArcInfoBuiltOn(info);
		float x, y;
		inCurve.GetPointAtParameter(t, x, y);
		float s = arcInfo->arc.ParameterAtPoint(x, y);
		if (0 > s)
		{
			continue;
		}
		
		if (kInvalidIndex == arcInfo->indexT)
		{
			arcInfo->indexT = mTPointInfos.size();
			TPointInfo tpi = {arcInfo, inCurve, x, y, t, s, false};
			mTPointInfos.push_back(tpi);
			continue;
		}
		TPointInfo& tInfo = mTPointInfos[arcInfo->indexT]; 
		if (s > tInfo.s)
		{
			tInfo.curve = inCurve;
			tInfo.x = x;
			tInfo.y = y;
			tInfo.t = t;
			tInfo.s = s;
		}
	}
}

static bool GetIntersection(const ContourDot* inDot1, 
	const ContourDot* inDot2, float inLimitingFactor,
	float& outX, float& outY)
{
	float v1x = inDot1->GetVx();
	float v1y = inDot1->GetVy();
	float v2x = -inDot2->GetVx();
	float v2y = -inDot2->GetVy();
	float s = v1x * v2y - v1y * v2x;
	if (0 == s)
	{
		return false;
	}
	float dx = inDot2->GetX() - inDot1->GetX();
	float dy = inDot2->GetY() - inDot1->GetY();
	float t = (dx * v2y - dy * v2x) / s;
	if (0 >= t) 
	{
		return false;
	}
	float limitT = inLimitingFactor * (inDot1->GetOuterHalfsize() 
		+ inDot2->GetOuterHalfsize());
	if (t > limitT)
	{
		return false;
	}
	float t2 = (dx * v1y - dy * v1x) / s;
	if (0 < t2 && t2 < limitT)
	{
		outX = inDot1->GetX() + t * v1x;
		outY = inDot1->GetY() + t * v1y;
		return true;
	}
	return false;
}


void StrokeVertexesFinder::AddCorner(const ContourDot* inPrev3,
		const ContourDot* inPrev2, const ContourDot* inPrev1, 
		const ContourDot* inDot, const Stroke& inStroke, int inIndex)
{
	float lastK = ::fabs(inDot->GetCurvature());
	float prev1K = ::fabs(inPrev1->GetCurvature());
	if (prev1K < 2.0f * lastK || 
		0.1f > prev1K * inPrev1->GetOuterHalfsize() ||
		NULL == inPrev2)
	{
		return;
	}
	float prev2K = ::fabs(inPrev2->GetCurvature());
	if (prev2K < 0.3f * prev1K && lastK < 0.3f * prev1K)
	{
		// corner with one contour dot at the top
		CornerInfo ci;
		if (GetIntersection(inPrev2, inDot, 3.0f, ci.x, ci.y))
		{
			ci.dot1 = inPrev2;
			ci.dot2 = inDot;
			ci.stroke = &inStroke;
			ci.index1 = inIndex - 2;
			ci.index2 = inIndex;
			mCorners.push_back(ci);
		}
	}
	else if (prev2K >= 2.0 * lastK && NULL != inPrev3)
	{
		float prev3K = ::fabs(inPrev3->GetCurvature());
		if (prev2K < 2.0f * prev3K ||
			0 > inPrev1->GetCurvature() * inPrev2->GetCurvature())
		{
			return;
		}
		// corner with two contour dots at the top
		CornerInfo ci;
		if (GetIntersection(inPrev3, inDot, 4.0f, ci.x, ci.y))
		{
			ci.dot1 = inPrev3;
			ci.dot2 = inDot;
			ci.stroke = &inStroke;
			ci.index1 = inIndex - 3;
			ci.index2 = inIndex;
			mCorners.push_back(ci);
		}
	}
}

void StrokeVertexesFinder::AddEndsMeeting(const Stroke& inStroke,
	int inStrokeEnd)
{
	const ContourDot* dot = inStroke.GetContourDotAt(inStrokeEnd);
	if (!mNeighborEnumerator.SelectNeighbors(*dot, true))
	{
		return;
	}
	const NeighborEnumerator::Info* info1 = 
		mNeighborEnumerator.GetInfoForStrokeEnd(&inStroke, inStrokeEnd);
	assert(NULL != info1);

	ArcInfo* arcInfo1 = GetArcInfoBuiltOn(info1);

	while (const NeighborEnumerator::Info* info2 = 
		mNeighborEnumerator.FindNextNeighbor())
	{
		ArcInfo* arcInfo2 = GetArcInfoBuiltOn(info2);

		if (kDiscrepancyCriterion > 
			arcInfo1->arc.DiscrepancyWithArc(arcInfo2->arc))
		{
			// add junction
			const ContourDot* dot1 = info1->dot;
			const ContourDot* dot2 = info2->dot;
			float s1 = arcInfo1->arc.ParameterAtPoint(dot2->GetX(), dot2->GetY());
			float s2 = arcInfo2->arc.ParameterAtPoint(dot1->GetX(), dot1->GetY());
			if (s1 > mLimitForArcParameter && s2 > mLimitForArcParameter)
			{
				mJunctions.push_back(JunctionInfo(arcInfo1, arcInfo2));
			}
			continue;
		}

		TwoEndsInfo endsInfo;
		bool isIntersecting = arcInfo1->arc.FindIntersection(arcInfo2->arc,
			mLimitForArcParameter,
			endsInfo.x, endsInfo.y, endsInfo.s1, endsInfo.s2);
		if (!isIntersecting)
		{
			continue;
		}
		int currentAppendIndex = mTwoEndsInfos.size();
		endsInfo.arcInfo1 = arcInfo1;
		if (kInvalidIndex == arcInfo1->firstIndex)
		{
			arcInfo1->firstIndex = currentAppendIndex;
		}
		else
		{
			mTwoEndsInfos[arcInfo1->lastIndex].next1 = currentAppendIndex;
		}
		arcInfo1->lastIndex = currentAppendIndex;

		endsInfo.arcInfo2 = arcInfo2;
		if (kInvalidIndex == arcInfo2->firstIndex)
		{
			arcInfo2->firstIndex = currentAppendIndex;
		}
		else
		{
			mTwoEndsInfos[arcInfo2->lastIndex].next2 = currentAppendIndex;
		}
		arcInfo2->lastIndex = currentAppendIndex;
		endsInfo.next1 = endsInfo.next2 = kInvalidIndex;
		endsInfo.isDeleted = false;
		mTwoEndsInfos.push_back(endsInfo);
	}
}

StrokeVertexesFinder::ArcInfo* StrokeVertexesFinder::GetArcInfoBuiltOn(
	const NeighborEnumerator::Info* inInfo)
{
	InfoMap::const_iterator i = mMap.find(inInfo);
	if (i != mMap.end())
	{
		return i->second;
	}
	mArcInfos.push_back(ArcInfo(inInfo));
	ArcInfo* arcInfo = &mArcInfos.back();
	mMap[inInfo] = arcInfo;
	return arcInfo;
}


DistinctivePoint* StrokeVertexesFinder::GetTPoints(
	DistinctivePoint* ioBuffer) const
{
	DistinctivePoint* q = ioBuffer;
	TPointCollection::const_iterator itp = mTPointInfos.begin();
	for (; itp != mTPointInfos.end(); ++itp)
	{
		if (!itp->isDeleted)
		{
			float x = itp->x;
			float y = itp->y;

			q->SetPosition(x, y);
			q->SetCurveParameter(itp->t);

			float dx, dy;
			itp->curve.GetDirectionAtParameter(itp->t, dx, dy);
			const Stroke* stroke = itp->curve.GetStroke();
			int strokeEnd = itp->curve.GetStrokeEnd();
			q->AddDirection(dx, dy, stroke, strokeEnd);
			AddDirectionToDistinctivePoint(*q, *(itp->arcInfo), x, y);
			++q;
		}
	}
	return q;
}

DistinctivePoint* StrokeVertexesFinder::GetEndsMeetings(
	DistinctivePoint* ioBuffer) const
{
	DistinctivePoint* q = ioBuffer;
	std::deque<TwoEndsInfo>::const_iterator ipp = mTwoEndsInfos.begin();
	for (; ipp != mTwoEndsInfos.end(); ++ipp)
	{
		if (!ipp->isDeleted)
		{
			float x = ipp->x;
			float y = ipp->y;
			q->SetPosition(x, y);
			AddDirectionToDistinctivePoint(*q, *(ipp->arcInfo1), x, y);
			AddDirectionToDistinctivePoint(*q, *(ipp->arcInfo2), x, y);
			++q;
		}
	}
	return q;
}

DistinctivePoint* StrokeVertexesFinder::GetCorners(
	DistinctivePoint* ioBuffer) const
{
	DistinctivePoint* q = ioBuffer;
	CornerCollection::const_iterator ic = mCorners.begin();
	for (; ic != mCorners.end(); ++ic, ++q)
	{
		q->SetPosition(ic->x, ic->y);
		q->AddDirection(-ic->dot1->GetVx(), -ic->dot1->GetVy(), 
			ic->stroke, ic->index1);
		q->AddDirection(ic->dot2->GetVx(), ic->dot2->GetVy(),
			ic->stroke, ic->index2);
	}
	return q;
}

void StrokeVertexesFinder::AddDirectionToDistinctivePoint(
	DistinctivePoint& outDistinctivePoint, const ArcInfo& inFromInfo,
	float inX, float inY) const
{
	float dx, dy;
	inFromInfo.arc.GetTangentVectorAtPoint(inX, inY, dx, dy);
	outDistinctivePoint.AddDirection(-dx, -dy, inFromInfo.info->stroke,
		inFromInfo.info->strokeEnd);
}

inline
float StrokeVertexesFinder::GetSavedScalarProduct(int inIndex) const
{
	return mSavedScalarProducts[inIndex & 3];
}

///////////////////////////////////////////////////////////////////////////////
inline 
int StrokeVertexesFinder::TwoEndsInfo::NextIndexFor(
	const ArcInfo* inArcInfo) const
{
	return (arcInfo1 == inArcInfo ? next1 : next2);
}

inline 
bool StrokeVertexesFinder::TwoEndsInfo::DeleteIfSmallerParameter(
	const ArcInfo* inArcInfo, float inParameterLimit)
{
	float s = (arcInfo1 == inArcInfo ? s1 : s2);
	if (s <= inParameterLimit)
	{
		isDeleted = true;
	}
	return isDeleted;
}

